1. Field of the Invention
The present invention relates to performing a fixed codebook search of an enhanced variable-rate Codec (EVRC).
2. Background of the Related Art
The IS-127 EVRC was adopted as an 8 kbps voice encoder standard of TIA/EIA in 1996 and is being considered for use as a standard encoder in CDMA 2000. The IS-127 EVRC, which has been used in CDMA digital cellular systems, is a high performance voice encoder which provides toll quality second to 13 kbps Qualcomm code excited linear prediction (QCELP) used in PCS communications.
The EVRC has three data rates, namely a maximum data rate (Rate1, 8 kbps), an intermediate data rate (Rate1/2, 4 kbps), and a minimum data rate (Rate1/8, 1 kbps). It employs an encoding process which includes performing adaptive and fixed codebook searches for linear prediction and excited signal quantization. At this time, the fixed codebook search requires the highest computational complexity and occupies at least 40% of the whole encoding process.
More specifically, when voice information is inputted, an analyzer extracts a linear predictive coefficient (LPC), a pitch element (adaptive codebook search) and an energy, namely residual element (fixed codebook search). The fixed codebook search of the EVRC is based on an algebraic code-excited linear prediction (ACELP). The maximum data rate (Rate1) generates the highest computational complexity during the fixed codebook search.
FIG. 1 is a table showing each pulse position of an algebraic codebook at the maximum data rate of the EVRC. This fixed codebook is a 35-bit algebraic codebook at the maximum data rate (Rate1). In this codebook, all codebook vectors include eight pulses having a size of ±1, and a length thereof is 55 (0, 1, 2, . . . , 55). Its determinant is represented by [55×1]t.
One sub frame is randomly divided into five tracks T0, T1, T2, T3 and T4 each having eleven pulse positions. The eleven pulses (0, 5, 10, . . . , 50), (1, 6, 11, . . . , 51), (2, 7, 12, . . . , 52), (3, 8, 13, . . . , 53) and (4, 9, 14, . . . 54) of the five tracks are randomly set up and searched, and thus tracks including two pulses and tracks including one pulse exist in the five tracks. That is, the five tracks T0, T1, T2, T3 and T4 are combined to generate double-pulse per track including two pulses and single-pulse per track including one pulse.
FIG. 2 is a table showing codewords for track orders. In the fixed codebook at Rate1, numbers of cases of the double-pulse tracks and single-pulse tracks are divided into four codewords 00, 01, 10 and 11, and pulse searches are performed on every codeword. A code having the greatest codebook gain is selected, and its pulse position, pulse code and codebook gain are determined as optimal fixed codebook parameters. It is therefore evident that performing pulse searches (double-pulse track and single-pulse track) in this manner on four-track configuration codewords is very complicated.
More specifically, when the track configuration codeword is ‘00’, a double-pulse per track order is T0-T1-T2 and a single-pulse per track order is T3-T4 in the five tracks. When the track configuration codeword is ‘01’, the double-pulse per track order is T1-T2-T3 and the single-pulse per track order is T4-T0. When the track configuration codeword is ‘10’, the double-pulse per track order is T2-T3-T4 and the single-pulse per track order is T0-T1. And, when the track configuration codeword is ‘11’, the double-pulse per track order is T3-T4-T0 and the single-pulse per track order is T1-T2.
In the single-pulse track, one of T3-T4, T4-T0, T0-T1 and T1-T2 is selected, encoded using a 2-bit (P6, P7) codeword, and transmitted to a receiving end. In the double-pulse track, two pulse positions and codes are encoded each using an 8-bit codeword (P0, P1), (P2, P3) and (P4, P5). Accordingly, a total of 35-bits {=2+(7+2)+(8×3)} are necessary for the encoding process of the algebraic codebook.
The EVRC fixed codebook is an algebraic codebook which has advantages in storage performance and computational complexity. The structure of the EVRC fixed codebook is based on an interleaved single-pulse permutation (ISPP) design. The codebook search is a process for searching a codebook factor and a codebook gain which minimizes a weighted mean square error between an original signal and a combined signal, and is performed in sub frame units.
FIG. 3 is a flowchart showing a conventional fixed codebook search of the EVRC. This algebraic codebook search involves searching the algebraic codebook to minimize the mean square error between the weighted original signal and the weighted combined signal. For this, a fixed codebook object signal (xw)[N×1] and an impulse response matrix H[N×N] are obtained through LPC analysis, residual signal correction, and adaptive codebook search processes.
In an initial step of the method, a vector dot product (d)[N×1] and an autocortelation function (φ)[N×N] are calculated using the fixed codebook target signal and the impulse response matrix (S301). That is, the vector d is calculated by multiplying the impulse response matrix H by the fixed codebook object signal xw, and the autocorrelation function φ is calculated by mutually multiplying the impulse response matrix H.
Next, a pulse sign (±1) is determined in pulse positions existing in each track (S302). The pulse sign is previously determined according to code information of a reference signal which is a weighted sum of the object signal x(n) of a residual domain and the vector dot product d.
Finally, after the pulse code is determined, an optimal pulse position is searched from the vector dot product d which is a signal backward-filtered from each codeword and the autocorrelation function φ (S303). This procedure is repeated to search the pulse positions. That is, the optimal pulse for each codeword 00, 01, 10 and 11 is searched by using the calculated vector dot product, autocorrelation function and pulse code determined in every pulse position.
The codebook search is identical to the process for searching a code vector Ck maximizing a search standard Tk as represented by Formula 1:
                              T          k                =                                            (                                                d                  t                                ⁢                                  c                  k                                            )                        2                                              c              k              t                        ⁢            Φ            ⁢                                                  ⁢                          c              k                                                          (        1        )            
Here, the vector dot product (d=Htxw) is a backward filtered signal obtained by passing the given object signal (xw)[N×1] through the weighted combined filter H[N×N], the autocorrelation function (φ=HtH) is an impulse response correlation matrix of the weighted combined filter, and k is a number of cases.
The vector dot product (d)[N×1] and the autocorrelation function (φ)[N×N] are previously calculated before the codebook search, and computational complexity thereof is in proportion to a square of a length of the sub frame.
In the EVRC, the pulse sign (±1) is predetermined in each position of the tracks to simplify the codebook search for determining the optimal codebook vector. The optimal pulse position is then obtained based on Formula 1.
FIG. 4 shows steps included in the conventional fixed codebook search of the EVRC. In the first step, the fixed codebook object signal xw and the impulse response matrix H are obtained through an LPC analysis and residual signal correction and adaptive codebook search processes (S401).
In the second step, the backward filtered target vector dot product d and the autocorrelation function φ are calculated using the fixed codebook object signal xw and the impulse response matrix H of the first step as represented by Formula 2 (S402):d=Htxwφ=HtH  (2)
In the third step, the pulse sign (±1) is determined by using the vector dot product d of the second step (S403).
In the four given track configuration codewords (jth=0, 1, 2, 3) of FIG. 2, the pulse searches are respectively done on the pulse positions of the given tracks T0, T1, T2, T3 and T4 of FIG. 1, and the track configuration codeword maximizing the search standard Tk in Formula 1 is selected. That is, when the codeword order jth is ‘0’, the five tracks T0, T1, T2, T3 and T4 are combined in the 0th codeword, and the pulse searches of the double-pulse track T0-T1-T2 including two pulses and the single-pulse track T3-T4 including one pulse are done on the 0th codeword combination configuration track (S404). In the same manner, the pulse searches of the double-pulse track and the single-pulse track which satisfy each codeword combination configuration track are sequentially performed in the succeeding codeword orders jth=1(01), jth=2(10) and jth=3(11) (S405–S407).
After the pulse searches are done in each codeword order, when the search codeword Jth exceeds 3(11), the codeword order jth having the greatest codebook gain, namely the codeword Ck maximizing the search standard Tk in Formula 1, is selected in the fourth step (S408). When the codeword is selected, the pulse position, pulse code and codebook gain of the corresponding track configuration codeword are determined as the optimal fixed codebook parameters (S409). That is, in the fourth step, the pulse position, pulse sign (±1) and codebook gain (scale) of the track configuration codeword c calculated in the third step are determined as the optimal fixed codebook parameters.
The process for obtaining the fixed codebook object signal xw and the impulse response matrix H through LPC analysis and residual signal correction and adaptive codebook search processes has been generally performed and therefore a detailed explanation is omitted. Also generally performed is the process for selecting the track configuration codeword that maximizes the search standard Tk in Formula 1 by doing pulse searches on the pulse positions of the tracks T0, T1, T2, T3 and T4 of FIG. 1 in four given track configuration codewords (jth=0, 1, 2, 3), using the vector dot product d, the autocorrelation function φ and the pulse code (±1) determined by using the vector dot product d. A detailed explanation of this process is therefore also omitted.
In the conventional fixed codebook search performed at the maximum data rate, the track configuration codeword searches of FIG. 2 and the pulse position searches of FIG. 1 in each codeword double-pulse track and single-pulse track must be performed. This increases computational complexity. More specifically, as described above, the numbers of cases of the double-pulse tracks and the single-pulse tracks are divided into four codewords, and the pulse searches are done on each codeword. The codeword having the greatest codebook gain is then selected and its pulse position, pulse code and codebook gain are determined as optimal fixed codebook parameters. The pulse searches must therefore be performed on the four track configuration codewords. This increases computational complexity and therefore adversely affects the overall cost and efficiency of the system.